In order to synchronize the access to an object in a program that runs a plurality of threads, the program code is so designed that before an object is accessed it is locked, then it is accessed, and thereafter it is unlocked. A spin lock and a queue lock are well known as object locking methods. In addition, a combination of these locking methods (hereinafter, referred to as hybrid lock) has recently been proposed. Brief explanations for these object locking methods will now be given.
(1) Spin Lock
A spin lock system is a system wherein the identifier of a thread which acquires a lock of an object is stored in consonance with the object so as to manage the locking state. With the spin lock system, when thread T fails to acquire a lock of an object o, i.e., when another thread S has already locked the object o, thread T repeats the locking process until it acquires a lock. Specifically, an atomic machine instruction, such as compare_and_swap, is employed to lock or unlock an object in the following manner.
TABLE 110:/* lock */20:while (compare_and_swap(&o−>lock, 0, thread_id( ))==0)30: yield( );40:/* access to o */. . .50:/* unlock */60:o−>lock=0;
Object locking is performed at lines 20 and 30. The function yield( ) is repeated until a lock is acquired. Here, yield( ) is used to halt the running of the current thread and to shift control to a scheduler. While normally a scheduler selects and runs one of several executable threads, in the long run, the scheduler runs the original thread and repeats the execution of the “while” loop until it has acquired a lock. When “yield” is present, not only are CPU resources wasted, but also the performance of the method must depend on a platform scheduling system, so that it is difficult to write a desirable program. At compare_and_swap in line 20, which is the condition provided for the “while” statement, the contents of the field “o->lock,” which is prepared for object o, are compared with 0. If the result of the comparison is true, the ID of the thread (thread_id( )) is written to that field. Therefore, when 0 is stored in the field prepared for object o, it indicates that an object has not been locked by a thread. To unlock an object, as in line 60, 0 is stored in the field “o->lock”. In this case, this field is, for example, one word, but the number of bits that is actually required is that which will suffice for the storage of an identifier of a thread.
(2) Queue Lock
A queue lock system is a locking system for employing a queue to manage a thread which accesses to an object. With the queue lock method, when thread T fails to lock an object o, thread T adds itself to the queue of the object o and suspends its execution. The code for unlocking an object includes a code that is used to examine a queue to determine whether it is empty. When the queue is not empty, one thread is extracted from the queue and its execution is resumed. This queue lock system is implemented together with the scheduling mechanism for an operating system (OS), and is provided as the API (Application Programming Interface) of the OS. For example, a semaphore or a Mutex variable constitutes a typical queue lock. In the queue lock system, the space overhead required exceeds one word, and normally is nearer twenty bytes. In addition, since a queue that is a common resource is operated internally by lock and unlock functions, this acquisition or the release of a specific lock should also be noted.
(3) Hybrid Lock
A multi-thread program is so written that access to a common resource should be protected by a lock, while taking into account the fact that the execution of the program will be performed by multiple threads. However, in some cases, multi-thread libraries are employed by single-thread programs, and even when the execution of a multi-thread program is performed by running multiple threads, a multi-thread contention of locks seldom occurs. Actually, according to the execution profile in a Java (trademark of Sun Microsystems Inc.) program, among many applications, contention of accesses to an object seldom occurs.
Therefore, it is considered that a very frequently executed path is one for “locking an unlocked object, accessing to it and unlocking it.” But while this path is executed extremely efficiently in the spin lock system, it is less efficiently executed in the queue lock system, as to both time and space. On the other hand, when a contention actually occurs, even though this is seldom, CPU resources are wasted in the spin lock system, while such waste does not occur in the queue lock system.
According to the basic idea of the hybrid lock system, a simple lock system, such as that represented by a spin lock (hereinafter referred to as a light-weight lock), is combined with a complicated lock system, such as that represented by a queue lock (hereinafter referred to as a heavy-weight lock), so that the above frequently executed path is performed at a high speed, and the efficiency of the processing is maintained, even when a contention occurs. Specifically, the processing of a light-weight lock is performed first and, if a contention occurs, the operation is shifted to the processing of a heavy-weight lock, after this, only the processing of a heavy-weight lock is employed.
In the hybrid lock system, as well as in the spin lock system, a lock field is present in an object. A value of a “thread identifier,” or of a “heavy-weight lock identifier,” and a Boolean value indicating which value is stored are entered in the field.
The locking procedure is as follows.    1) Acquisition of a light-weight lock is attempted in accordance with an atomic instruction (e.g., compare_and_swap). If the light-weight lock is acquired, an access to an object is executed. When the acquisition of a light-weight lock fails, it is assumed that a heavy-weight lock has already been acquired, or that although a light-weight lock is being used, the light-weight lock has already been acquired by another thread.    2) If the processing has already been shifted to the heavy-weight lock, the heavy-weight lock is acquired.    3) When contention occurs during the acquisition of the light-weight lock, first the light-weight lock is acquired and then the processing is shifted to the heavy-weight lock, which is acquired in turn (in the following explanation, the processing in 3) is executed during the “inflate” function).
There are two types of implementations of the hybrid lock, depending on whether or not a “yield” occurs upon the “acquisition of the light-weight lock.” A detailed explanation for this will now be given. It should be noted that a lock field occupies a space whose size is a word. Further, to simplify the explanation, assume that the “thread identifier,” or the “heavy-weight lock identifier,” is in all cases an even number other than 0. When the least significant bit of the lock field is 0, the “thread identifier” value is stored in the field, and when the least significant bit is 1, the “heavy-weight lock identifier” value is stored.